package cn.xaut.剑指offer.m01;

import java.util.*;

/**
 * 剑指 Offer 03. 数组中重复的数字
 */
public class demo06 {

    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        for (int x : nums) {
            if (!set.add(x))
                return x;
        }
        return -1;
    }


    public int findRepeatNumber2(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }

        List<Integer> list = new ArrayList<>();
        
        return -1;
    }


    /**
     * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
     * 返回描述：
     * 如果数组中有重复的数字，函数返回true，否则返回false。
     * 如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public boolean duplicate(int numbers[],int length,int [] duplication) {

        if (length == 0) {
            duplication[0] = -1;
            return false;
        }
        
        Set<Integer> set = new HashSet<Integer>();
        for (int x : numbers) {
            if (!set.add(x)) {
                duplication[0] = x;
                return true;
            }
        }
        return false;
    }
}
